package ch09_;

public class Ch9_7 {
	/**
	public int ways(int n) {
		int[] a = new int[n + 1];
		a[0] = 1;
		for (int i = 1; i <= n; i++) {
			a[i] = (bound(a, i - 1)) + (bound(a, i - 5)) + (bound(a, i - 10))
					+ (bound(a, i - 25));
		}

		// for (int i = 0; i <= n; i++) {
		// System.out.print(a[i] + " ");
		// }
		return a[n];
	}

	private int bound(int[] a, int i) {
		if (i < 0 || i >= a.length) {
			return 0;
		} else {
			return a[i];
		}
	}
	*/
	public enum Denom{
		QUARTER, DIME, NICKEL, PENNY
	}
	
	public int ways(int n) {
		return ways(n, 25);
	}
	
	private int ways(int n, int d) {
		if (n < d && d == 1) return 0;
		if (n == 0) return 1;
		if (n == d) return 1;
		int result = 0;
		if (d >= 1) {
			result += ways(n - d, 1);
		}
		if (d >= 5) {
			result += ways(n - d, 5);
		}
		if (d >= 10) {
			result += ways(n - d, 10);
		}
		if (d >= 25) {
			result += ways(n - d, 25);
		}
		return result;
	}

	public static void main(String[] args) {
		Ch9_7 test = new Ch9_7();
		int n = 5;
		System.out.println(test.ways(n));
	}
}
